package lru

import "container/list"

type Value interface {
	Len() int
}

type Cache struct {
	maxBytes		int64
	nbytes			int64
	ll 				*list.List
	cache 			map[string]*list.Element
	OnEvicted 		func(key string, value Value)
	// value是实现了Value接口的任意类型，该接口只包含了一个方法Len() int，用于
	// 返回值所占的内存大小
}

type entry struct {
	key 	string
	value 	Value
}

func New(maxBytes int64, OnEvicated func(string, Value)) *Cache {
	return &Cache{
		maxBytes: maxBytes,
		ll:		list.New(),
		cache: make(map[string]*list.Element),
		OnEvicted: OnEvicated,
	}
}

// find
// if the node which mapping the key exists, then move this node to end of the list
// Here, use front as the "End"
func (c *Cache) Get(key string) (value Value, ok bool) {
	if ele, ok := c.cache[key]; ok {
		c.ll.MoveToFront(ele)
		kv := ele.Value.(*entry)
		return kv.value, true
	}
	return
}

// delete
func (c *Cache) RemoveOldest()  {
	// 取到队首节点，删除，注意，这里用front作为队尾，back作为队首
	ele := c.ll.Back()
	if ele != nil {
		c.ll.Remove(ele)
		kv := ele.Value.(*entry)
		// 从字典中c.cache删除该节点的映射关系
		delete(c.cache, kv.key)
		// 更新当前所用的内存
		c.nbytes -= int64(len(kv.key)) + int64(kv.value.Len())
		// 如果回调函数`OnEvicted` 不为nil，调用
		if c.OnEvicted != nil {
			c.OnEvicted(kv.key, kv.value)
		}
	}
}

// Add
func (c *Cache) Add(key string, value Value)  {
	if ele, ok := c.cache[key]; ok {
		c.ll.MoveToFront(ele)
		kv := ele.Value.(*entry)
		c.nbytes += int64(value.Len()) - int64(kv.value.Len())
		kv.value = value
	} else {
		ele := c.ll.PushFront(&entry{key, value})
		c.cache[key] = ele
		c.nbytes += int64(len(key)) + int64(value.Len())
	}
	// 做完增加操作之后，如果当前使用内存nbytes超过了最大内存maxBytes
	// 删除最老的节点
	for c.maxBytes != 0 && c.maxBytes < c.nbytes {
		c.RemoveOldest()
	}
}

// Len() return the number of cache entries
func(c *Cache) Len()  int{
	return c.ll.Len()
}